package LeetCode1;

//根据中序和后续还原二叉树
public class Num106 {
    private static int index = 0;

    public static void main(String[] args) {
        int[] a = {9,3,15,20,7};
        int[] b = {9,15,7,20,3};
        buildTree(a,b);
    }
    public static TreeNode buildTree(int[] inorder, int[] postorder) {
        revers(postorder);
        return buildTreeHelper(inorder, postorder, 0, postorder.length - 1);
    }

    private static void revers(int[] postorder) {
        int start = 0;
        int end = postorder.length - 1;
        while (start < end) {
            int temp = postorder[start];
            postorder[start] = postorder[end];
            postorder[end] = temp;
            start++;
            end--;
        }
    }

    private static TreeNode buildTreeHelper(int[] inorder, int[] postorder, int left, int right) {
        if (left > right) {
            return null;
        }
        if (index < 0) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[index]);
        index++;
        int pos = findNode(inorder, root.val);
        root.right = buildTreeHelper(inorder, postorder, pos + 1, right);
        root.left = buildTreeHelper(inorder, postorder, left, pos - 1);
        return root;
    }

    private static int findNode(int[] inorder, int val) {
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == val) {
                return i;
            }
        }
        return -1;
    }
}
